# -*- coding:utf-8 -*-
# !/usr/bin python3
# Import exceptions.Empty
from exceptions.empty import Empty

"""用循环链表实现队列"""


class CircularQueue:
    """通过循环链表存储方式实现队列"""

    class _Node:
        """不共有类：用于存储单个链表结点"""

        __slot__ = "_element", "_next"

        def __init__(self, element, next_node):
            self._element = element
            self._next = next_node

    def __init__(self):
        self._tail = None
        self._size = 0

    def __len__(self):
        return self._size

    def is_empty():
        # return self._size == 0
        return self._size == 0

    def first(self):
        if self.is_empty():
            raise Empty("Queue is empty")
        return self._tail._next._element

    def last(self):
        if self.is_empty():
            raise Empty("Queue is empty")
        return self._tail._element

    def enqueue(self, e):
        new = self._Node(e, None)
        if self.is_empty():
            new._next = new
        else:
            new._next = self._tail._next
            self._tail._next = new
        self._tail = new
        self._size += 1

    def dequeue(self):
        if self.is_empty():
            raise Empty("Queue is empty!")
        old_head = self._tail._next
        if self._size == 1:
            self._tail = None
        else:
            self._tail._next = old_head._next
        self._size -= 1
        return old_head._element

    def rotate(self):
        if self._size > 0:
            self._tail = self._tail._next
